面试经验分享之数据结构、算法题
面试 IT 企业的研发岗位，数据结构和算法显然是必考的项目。俺只学过普通的数据结构课程，没读过 STL，也没有过 ACM 的训练和比赛经历，在一开始面对这样类型题目的时候，心里还是十分忐忑的。大大小小几十场面试下来，自己在这方面总算有了一定的心得积累，在此抛砖引玉，以飨读者。
在正式介绍题目和准备方法之前，有两点需要说明，
●Google 和 Facebook 这类对算法有很高要求的公司的在线测试我没有参加过（不过在牛人内推帮助下有过面试体验……），这超出了我目前的编码能力范围，网上有不少拿到 Google、Facebook offer 的经验总结文章，可以移步观赏；
●前段时间在微博上又看到有人说自己把 leetcode 刷了好几遍，不过一些转发评论者觉得， IT 公司面试中的算法考察没有价值，一来工作里用不太上，二来把程序员素质考察搞成了应试教育，他们认为更重要的是应聘者的工程能力。遇到这样的讨论，我一般喜欢和一把稀泥。若干年前， Google、微软的面试题让大家眼前一亮，觉得能选拔出个性十足的聪明人来，不过随着大家对这类题目的适应，可能选拔出来的人也在趋同，至少很多人都会在面试前用心准备，据报道 Google 最近也是放弃了这类面试题目。没有什么一劳永逸、一成不变的考查方式，毕竟面试是人和人之间的动态“较量”。不要贪恋算法的奇技淫巧，也不要因为题目筛选力度的衰减而否定考察初衷。面试不仅是考验求职者，也同样在考验面试官，如果问的都是老题儿，那本山大叔肯定都会抢答了。
言归正传，以下分数据结构题目、算法题目、开放题目三部分来介绍我在面试中碰到的问题。
数据结构题目
概述
虽然课本由简到繁、由难到易地介绍了诸多数据结构，我在面试中被问到的却还都是基本类型，比如堆栈、队列、链表、二叉树。题目主要有两类，数据结构实现和具体情境下数据结构的应用。
分类讨论
类型一：数据结构实现
1、实现 java.util.List 中的基础功能；
2、实现栈，使得 添加、删除、max 操作的复杂度为 O(1)（我脚着好像是不可实现的，想到最好的是添加、删除 O(log)， max 是 O(1)），实现见 正在努力减肥的胖子 同学给出的评论，参考 leetcode 中的这道题目，惭愧；
3、选取任意数据结构实现添加、删除、随机返回三个功能，分析复杂度；
4、用数组实现队列，各操作的复杂度分析。
类型二：数据结构应用
1、两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值；
2、用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环；
3、如何在语料中寻找频繁出现的字串，分析复杂度（tire树）；
4、中缀表达式转逆波兰表达式，逆波兰表达式求值；
5、数据解压缩，3(a4(ab)) -> aababababaababababaabababab；
6、二叉树的文件存储。
准备建议
上上之选当然是看《算法导论》，书 和 公开课 都算。时间精力不足又想临时抱佛脚，清华大学计算机系邓俊辉老师的 教材 是好选择，也可以看 公开课。注意熟记不同数据结构的不同操作的不同实现方式（比如 哈希表的插入删除查找）的复杂度分析，不管面试官给你出的题目是难是易，妥妥儿的会问复杂度。
算法题目
概述
有过面试经历的企业（BAT、小米、宜信、猿题库、FreeWheel等）当中，还没有谁问过我需要复杂算法（比方说 此链接 中的很多知识点）才能解决的问题。我遇到的算法题目大致可以分为两类：
●经典算法实现题 快速排序、归并排序、堆排序、KMP算法等都是重点，重要的是代码的正确性，其次是复杂度分析，当然，人家也不都是直接问你怎么实现这个具体算法，而是包装到情境里；
●思维益智题 考察你分析问题的能力，大部分可以归结到二分、动态规划、递归上，重要的是思路，其次是尽量低的复杂度，再次是代码的正确性。
下面具体介绍我遇到的两种类型题目中的问题。
分类讨论
类型一：经典算法实现题
1、实现快速排序、归并排序、堆排序，各排序算法复杂度分析；
2、实现KMP，解释原理；
3、迷宫的深度搜索、广度搜索；
4、写 find 函数，在目标串中匹配模式串（要考虑中文字符的情况）。
类型二：思维益智题
1、数列中找第 k 大的数字（与快排或堆排序有关）；
2、两个有序数组，寻找归并排序后数组的中位数/第 k 大数字（与二分有关）；
3、一维数组，swap 其中的几对数字（每个数字只属于一次 swap 操作），实现查找（与二分有关）；
4、一个有序数组，其中一个数字发生变异，但不知道变异后会不会影响整体序，如何实现查找；
5、二维数组，每行递增，每列递增
●实现查找；
●二维数组，每行递增，每列递增，求第 k 大的数；
●任意交换其中的两数，发现并恢复；
6、寻找字符串中第一个只出现一次的字符；
7、统计数列中的逆序对（归并排序有关）；
8、最长公共子串（动态规划有关）；
9、最大子序列和，允许交换一次的最大子序列和；
10、给定数组，寻找 next big（堆排序有关）；
11、一维有序数组，经过循环位移后，最小的数出现在数列中间
●如果原数组严格递增，如何找这个最小数；
●如果原数组严格递增或递减，如何找这个最小数；
●如果原数组非严格递增或递减，如何找这个最小数；
12、数组可能是递增、递减、递减后递增、递增后递减四种情况，递增递减都是非严格的，如果有转折点，返回转折点的值，否则返回-1；
13、单向网络，起点和终点唯一且连通，寻找那些一旦被删除将导致起点终点无法连通的点；
14、有序数组寻找和为某数的一对数字；
15、墙里能装多少水；
16、打印螺旋数组；
17、打印组合数；
18、字符数组，统计指定区间内的回文串个数。
准备建议
●不要纠结于是否是最佳思路，要保证能在 10-15 分钟内给出一个解决方案，并分析复杂度；
●基础的可以读读 @研究者July 的这本 电子书，更深入的可以阅读 CSDN 等博客中大牛们写的 ACM 解题报告；
●hihocoder、topcoder、leetcode、codility、POJ 等网站择一练手。
开放题目
这类开放题目让你自主选择数据结构，主要是考察求职者对于数据结构的特性与使用场景的综合理解，在面对具体应用场景时能否运用已有的数据结构和算法知识提出合理的解决方案。一般来说在这类问题里哈希表的出场率会比较高……例题如下
1、大数据量的 url log，怎么去重且统计每个 url 的出现次数，复杂度分析；
2、设计 cache 系统
●设计 cache 的接口；
●可以用什么数据结构实现；
●如何实现可伸缩的容量；
●cache 的空间管理策略，比如 cache 哪些条目，何时清理；
●cache 系统启动时分配多大的空间，之后按照怎样的策略增大；
3、设计爬虫；
4、流媒体播放客户端从多个完全相同的发送方接收视频包，同一发送方的包会按序到达，不同发送方的包则不一定，有可能会丢包，但还是要保证播放流畅度，设计播放客户端的算法。
总结
●数据结构和算法的基础知识还是十分重要的，大部分题目的思路来源于此；
●训练自己算法复杂度的分析能力，有的时候对复杂度的分析会反过来会帮助你找到更好的算法；
●一定量的题目积累很重要，就好像准备高考数学压轴题一样，见识的越多，思路来得越快，当然，前提是你能够不断总结反思。